package main.Q1201_1300;

import java.util.Arrays;

public class Q1291_1300 {
    public static void main(String[] args) {
        System.out.println("Question1291：");
        System.out.println("Question1292：元素和小于等于阈值的正方形的最大边长");
        System.out.println("Question1293：");
        System.out.println("Question1294：");
        System.out.println("Question1295：统计位数为偶数的数字");
        System.out.println("Question1296：");
        System.out.println("Question1297：");
        System.out.println("Question1298：");
        System.out.println("Question1299：");
        System.out.println("Question1300：转变数组后最接近目标值的数组和");
    }
}

class Question1292{
    public int process(int[][] mat,int row,int col,int threshold){
        int lastSum=mat[row][col],result=1,r=mat.length,c=mat[0].length;
        if (lastSum<=threshold){//满足
            while (true){
                result++;
                int temp=0;
                if (row+result-1<r&&col+result-1<c){//新扩展的边
                    for (int i=0;i<result;i++){
                        temp+=mat[row+i][col+result-1];
                    }
                    for (int i=0;i<result-1;i++){
                        temp+=mat[row+result-1][col+i];
                    }
                }else {
                    result--;
                    break;
                }
                if (lastSum+temp>threshold) {
                    result--;
                    break;
                }else lastSum+=temp;
            }
        }else result=-1;
        return result;
    }
    public int maxSideLength(int[][] mat, int threshold) {
        int result=0;
        for (int i=0;i<mat.length;i++){
            for (int j=0;j<mat[0].length;j++){
                if (mat[i][j]>threshold) continue;
                else {
                    int temp=process(mat,i,j,threshold);
                    result=Math.max(result,temp);
                }
            }
        }
        return result;
    }
}

class Question1295{
    public int findNumbers(int[] nums) {
        int count=0;
        for (int num:nums) {
            String s = String.valueOf(num);
            if (s.length()%2==0) count++;
        }
        return count;
    }
}

class Question1300{
    public int process(int[] preSum,int val,int[] arr,int target){
        int diff=0,left=0,right=arr.length,sum=0;
        if (arr[0]>val){
            sum=val*arr.length;
        }else {
            while (left<right){//首个大于val的值
                int mid=left+(right-left)/2;
                if (arr[mid]>val) right=mid;
                else left=mid+1;
            }
            int temp=preSum[left-1];
            sum=temp+(arr.length-left)*val;
        }
        diff=Math.abs(target-sum);
        return diff;
    }
    public int findBestValue(int[] arr, int target) {
        Arrays.sort(arr);
        int max=arr[arr.length-1],result=0,lastDiff=Integer.MAX_VALUE;
        int[] preSum=new int[arr.length];//前缀和
        for (int i=0;i<arr.length;i++){
            if (i==0) preSum[i]=arr[i];
            else preSum[i]=preSum[i-1]+arr[i];
        }
        for (int i=0;i<=max;i++){
            int diff=process(preSum,i,arr,target);
            if (diff<lastDiff){
                result=i;
                lastDiff=diff;
            }
            if (diff==0) break;
        }
        return result;
    }
}